// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

//----------------------------------------------------------------------------
template <class T>
MgcTClassHeap<T>::MgcTClassHeap (unsigned int uiQuantity,
    unsigned int uiGrowBy)
    :
    m_tArray(uiQuantity)
{
    assert( m_uiGrowBy > 0 );

    m_uiQuantity = uiQuantity;
    m_uiGrowBy = uiGrowBy;
}
//----------------------------------------------------------------------------
template <class T>
unsigned int MgcTClassHeap<T>::GetQuantity () const
{
    return m_uiQuantity;
}
//----------------------------------------------------------------------------
template <class T>
T& MgcTClassHeap<T>::operator[] (unsigned int uiIndex) const
{
    return m_tArray[uiIndex];
}
//----------------------------------------------------------------------------
template <class T>
void MgcTClassHeap<T>::Add (const T& rtRecord)
{
    if ( m_uiQuantity++ == m_tArray.GetQuantity() )
    {
        unsigned int uiNewQuantity = m_tArray.GetQuantity() + m_uiGrowBy;
        m_tArray.SetQuantity(uiNewQuantity,true);
    }

    int iChild = m_uiQuantity - 1;
    while ( iChild > 0 )
    {
        int iParent = (iChild-1)/2;
        if ( rtRecord <= m_tArray[iParent] )
            break;

        m_tArray[iChild] = m_tArray[iParent];
        iChild = iParent;
    }

    m_tArray[iChild] = rtRecord;
}
//----------------------------------------------------------------------------
template <class T>
void MgcTClassHeap<T>::Remove (T& rtMaximum)
{
    if ( m_uiQuantity == 0 )
        return;

    rtMaximum = m_tArray[0];

    int iLast = m_uiQuantity - 1;
    T tRecord = m_tArray[iLast];
    int iParent = 0, iChild = 1;
    while ( iChild <= iLast )
    {
        if ( iChild < iLast )
        {
            if ( m_tArray[iChild] < m_tArray[iChild+1] )
                iChild++;
        }

        if ( m_tArray[iChild] <= tRecord )
            break;

        m_tArray[iParent] = m_tArray[iChild];
        iParent = iChild;
        iChild  = 2*iChild + 1;
    }

    m_tArray[iParent] = tRecord;
    m_uiQuantity--;
}
//----------------------------------------------------------------------------
template <class T>
void MgcTClassHeap<T>::Build ()
{
    if ( m_uiQuantity <= 1 )
        return;

    int iLast = m_uiQuantity - 1;
    for (int iLeft = iLast/2; iLeft >= 0; iLeft--)
    {
        assert( IsValid(iLeft+1,iLast) );

        T tRecord = m_tArray[iLeft];
        int iParent = iLeft, iChild = 2*iLeft + 1;
        while ( iChild <= iLast )
        {
            if ( iChild < iLast )
            {
                if ( m_tArray[iChild] < m_tArray[iChild+1] )
                    iChild++;
            }

            if ( m_tArray[iChild] <= tRecord )
                break;

            m_tArray[iParent] = m_tArray[iChild];
            iParent = iChild;
            iChild = 2*iChild + 1;
        }

        m_tArray[iParent] = tRecord;
    }
}
//----------------------------------------------------------------------------
template <class T>
void MgcTClassHeap<T>::Sort ()
{
    if ( m_uiQuantity <= 1 )
        return;

    Build();

    for (int iRight = m_uiQuantity - 1; iRight > 0; /**/)
    {
        T tRecord = m_tArray[iRight];
        m_tArray[iRight] = m_tArray[0];
        if ( --iRight == 0 )
        {
            m_tArray[0] = tRecord;
            return;
        }

        int iParent = 0, iChild = 1;
        while ( iChild <= iRight )
        {
            if ( iChild < iRight )
            {
                if ( m_tArray[iChild] < m_tArray[iChild+1] )
                    iChild++;
            }

            if ( m_tArray[iChild] <= tRecord )
                break;

            m_tArray[iParent] = m_tArray[iChild];
            iParent = iChild;
            iChild <<= 1;
        }

        m_tArray[iParent] = tRecord;
    }
}
//----------------------------------------------------------------------------
template <class T>
bool MgcTClassHeap<T>::IsValid (int iStart, int iFinal)
{
    for (int iC = iStart; iC <= iFinal; iC++)
    {
        int iP = (iC-1)/2;
        if ( iP > iStart )
        {
            if ( m_tArray[iP] < m_tArray[iC] )
                return false;
        }
    }

    return true;
}
//----------------------------------------------------------------------------
template <class T>
bool MgcTClassHeap<T>::IsValid ()
{
    return m_uiQuantity <= 1 || IsValid(0,m_uiQuantity-1);
}
//----------------------------------------------------------------------------
